10456. Сервер

Амин и Мурад решили создать игровой сервер “Майнкрафт”. На свою грандиозную церемонию открытия они пригласили k гостей. Приглашенные гости живут в разных городах и при соединении к серверу (в зависимости от местоположения) будут иметь определенную задержку (ping). Амин и Мурад осознав потенциальную проблему решили выбрать самое оптимальное местоположение для сервера.

Есть n городов пронумерованных от 1 до n и m двухсторонних каналов передачи между этими городами. Подключиться к серверу можно только через эти каналы. Посредством этих каналов можно создать сообщение между любыми двумя городами. Однако, никакие два города не могут иметь больше одного напрямую соединяющего их канала и ни один город не имеет каналов, соединяющих город к самому себе. Для каждого канала так же дается время задержки w_i. И так, время задержки соединения от какого-либо города к серверу равняется наименьшей сумме задержек каналов на пути от этого города к серверу среди всех возможных путей.

Амин и Мурад хотят выбрать для сервера такой город, чтобы при соединении суммарная задержка соединений всех гостей была минимальной. Если сервер находится в городе в котором живет кто-либо из гостей, то задержка соединения для этого гостя будет равна 0.

Если можно выбрать несколько городов с минимальной суммарной задержкой, то Амин и Мурад выберут город с наименьшим номером. Необходимо найти город, который выберут Амин и Мурад и суммарную задержку соединения всех гостей к серверу.

Вход. В первой строке даны три целых числа n (1 ≤ n ≤ 10⁴), m (1 ≤ m ≤ 4 * 10⁴), k (1 ≤ k ≤ 100) – количество городов, каналов передачи и гостей соответственно. Во второй строке даны k разных чисел c_i (1 ≤ c_i ≤ n) – номера городов где живут гости. В каждой из последующих m строк даны три целых числа u_i, v_i, w_i (1 ≤ u_i, v_i ≤ n). Этими числами обозначается двухсторонний канал между городами u_i и v_i с задержкой соединения w_i (1 ≤ w_i ≤ 10⁴).

Выход. Выведите два целых числа – номер города где будет находиться сервер и суммарная задержка соединения всех гостей к этому серверу.

Пример входа	Пример выхода
5 6 3 1 2 5 1 2 10 1 4 3 2 4 2 2 5 8 3 4 5 3 5 3	2 13

РЕШЕНИЕ

графы - Дейкстра

Анализ алгоритма

Поскольку n ≤ 10⁴, то для представления графа воспользуемся списком смежности.

Запустим алгоритм Дейкстры из городов, в которых проживают гости. Вычислим сумму расстояний от каждой вершины до всех гостей. Вершина с наименьшей суммой и будет искомой. Если таких вершин несколько, то выбираем ту, которая имеет наименьший номер.

Отметим, что сервер не обязательно будет находится в городе где проживает один из гостей.

Пример

Граф, приведенный в примере, имеет вид:

Запустим алгоритм Дейкстры из вершин, где проживают гости: 1, 2 и 5. Запишем кратчайшие расстояние от каждого гостя до всех вершин.

Найдем сумму расстояний от каждой вершины до всех гостей. Наименьшая сумма расстояний равна 13. Наименьший номер вершины, для которой эта сумма достигается, равен 2.

Таким образом, сервер следует расположить в городе 2, растояние от него до гостей равно 5 + 0 + 8 = 13.

Реализация алгоритма

Объявим бесконечность.

#define INF 0x3F3F3F3F

Структура edge хранит информацию о ребре: в какую вершину node следует и вес dist ребра.

struct edge

{

int node, dist;

edge(int node, int dist) : node(node), dist(dist) {}

};

Компаратор для сортировки пар (node, dist) по убыванию dist.

bool operator< (edge a, edge b)

{

return a.dist > b.dist;

}

Объявим список смежности графа.

vector<vector<edge> > g;

Реализация алгоритма Дейкстры. На вход подаются граф g и начальная вершина start. Возвращаемым значением является массив d, где d[i] содержит кратчайшее расстояние от start до i.

void Dijkstra(vector<vector<edge> >& g, vector<int>& d, int start)

{

priority_queue<edge> pq;

pq.push(edge(start, 0));

d = vector<int>(n + 1, INF);

d[start] = 0;

while (!pq.empty())

{

edge e = pq.top(); pq.pop();

int v = e.node;

if (e.dist > d[v]) continue;

for (int j = 0; j < g[v].size(); j++)

{

int to = g[v][j].node;

int cost = g[v][j].dist;

if (d[v] + cost < d[to])

{

d[to] = d[v] + cost;

pq.push(edge(to, d[to]));

}

}

}

}

Основная часть программы. Читаем входные данные.

scanf("%d %d %d", &n, &m, &k);

c.resize(k);

for (i = 0; i < k; i++)

scanf("%d", &c[i]);

Читаем входной взвешенный граф.

g.resize(n + 1);

for (i = 0; i < m; i++)

{

scanf("%d %d %d", &a, &b, &w);

g[a].push_back(edge(b, w));

g[b].push_back(edge(a, w));

}

Запускаем алгоритм Дейкстры из городов, в которых проживают гости.

dp.resize(n + 1);

for (i = 0; i < k; i++)

{

Dijkstra(g, dist, c[i]);

for (j = 1; j <= n; j++)

dp[j] += dist[j];

}

На данный момент dp[i] хранит сумму кратчайших расстояний от вершины i до городов с гостями. Остается найти минимальное значение среди dp[i] и вывести требуемый ответ. Переменная ptr хранит наименьший номер вершины, в котором следует расположить сервер.

res = INF;

for (i = 1; i <= n; i++)

{

if (dp[i] < res)

{

res = dp[i];

ptr = i;

}

}

Выводим ответ.

printf("%d %d\n", ptr, dp[ptr]);